function Node(data, left, right) {
  this.data = data
  this.left = left
  this.right = right 
}

class BST {
  constructor() {
    this.root = null
  }

  insert(data) {
    const node = new Node(data, null, null)
    
    if(!this.root) {
      this.root = node
    } else {
      let current = this.root

      while(true) {
        if(current.data > data) {
          if(current.left === null) {
            current.left = node
            break
          } 
          current = current.left
        } else {
          if(current.right === null) {
            current.right = node
            break
          }
          current = current.right
        }
      }
    }
  }

  find(data) {
    let current = this.root
    while(true) {
      if(data === current.data) {
        return current
      }
      current = data < current.data ? current.left : current.right

      if(current === null) {
        return null
      }
    }
  }

  remove(data, node = this.root) {
    if(node === null) return null     
    
    if(data === node.data) {
      if(node.left === null && node.right === null) {
        return null
      }

      if(node.left === null) {
        return node.right
      }

      if(node.right === null) {
        return node.left
      }

      const tmpNode = node
      
      node.data = tmpNode.data
      node.right= this.remove(tmpNode.data, node.right)
      
      return node
    } else if(data < node.data) {
      node.left = this.remove(data, node.left)
      return node
    } else {
      node.right = this.remove(data, node.right)
      return node
    }

  }

  inOrder(node) {
    if(node) {
      this.inOrder(node.left)
      console.log(node.data)
      this.inOrder(node.right)
    }
  }

  preOrder(node) {
    if(node) {
      console.log(node.data)
      this.preOrder(node.left)
      this.preOrder(node.right)
    }
  }

  postOrder(node) {
    if(node) {
      this.postOrder(node.left)
      this.postOrder(node.right)
      console.log(node.data)
    }
  }

}


const bst = new BST()

bst.insert(1)
bst.insert(2)
bst.insert(3)
bst.insert(4)
bst.insert(5)
bst.insert(6)

bst.remove(6)

bst.inOrder(bst.root)
bst.preOrder(bst.root)
bst.postOrder(bst.root)


console.log(bst.find(1))
